﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
using Tron.DataStructures;

namespace Tron.Players.Search
{
    class IterativeDeepeningAlphaBetaSearchPlayer : Player
    {
        public static readonly int EMPTY_BLOCK = -2;

        public static readonly int DEFAULT_TURN_TIME = 200;
        public static readonly double POSITIVE_INFINITY = 1e9;
        public static readonly double NEGATIVE_INFINITY = -1e9;
        public static readonly double EPS = 1e-6;

        private double alpha;
        private double beta;

        private int opponentIndex;

        public IterativeDeepeningAlphaBetaSearchPlayer(int playerIndex)
            : this(playerIndex, DEFAULT_TURN_TIME)
        {

        }

        /**
         * <summary>Constructs an iterative deepening alpha beta search player
         * with the given player index and move time.</summary>
         * <param name="moveTime">The time in milliseconds that the player is given to
         * move</param> */
        public IterativeDeepeningAlphaBetaSearchPlayer(int playerIndex, int moveTime)
            : base(playerIndex)
        {

        }

        public override void Update(Percepts percepts, Actions actions)
        {
            if (percepts.PlayerStates.Count != 2)
            {
                throw new NotImplementedException();
            }

            opponentIndex = (PlayerIndex == 1) ? 0 : 1;

            Vector2 agentLoc = percepts.PlayerStates[PlayerIndex].Position;
            Vector2 opponentLoc = percepts.PlayerStates[opponentIndex].Position;

            int columns = percepts.Board.ColumnCount;
            int rows    = percepts.Board.RowCount;

            int[,] board = percepts.Board.GetCopyOfBoardArray();

            Console.WriteLine("Update");

            // set the action
            actions.MoveDirection = alphaBetaSearch(board,agentLoc,opponentLoc);
        }

        private Vector2 alphaBetaSearch(int[,] board, Vector2 agentLoc, Vector2 opponentLoc)
        {
            if (board == null)       throw new NullReferenceException("percepts is null");
            if (agentLoc == null)    throw new NullReferenceException("agentLoc is null");
            if (opponentLoc == null) throw new NullReferenceException("opponentLoc is null"); 
            
            //if (isTerminal(board,agentLoc,opponentLoc))
            //    throw new ArgumentException("Cannot start alpha beta search from a terminal state!");
           

            
            Vector2 bestMove = Vector2.UnitX;

            alpha = NEGATIVE_INFINITY;
            beta  = POSITIVE_INFINITY;

            double best  = NEGATIVE_INFINITY;

            foreach( Vector2 possibleMoveDirection in Constants.PossibleMoveDirections) {
                Vector2 newLocation = new Vector2(opponentLoc.X + possibleMoveDirection.X,opponentLoc.Y + possibleMoveDirection.Y);

                double v;

                if (isValid(board,newLocation))
                {
                    board[(int)newLocation.X, (int)newLocation.Y] = opponentIndex;
                    v = minValue(board, 0, agentLoc, newLocation);
                    board[(int)newLocation.X, (int)newLocation.Y] = EMPTY_BLOCK;
                }
                else
                {
                    v = utility(board, agentLoc, newLocation);
                }
                
                // Compute Max(v,best) and remember the corresponding "best move"
                if (v > best) {
                    bestMove = possibleMoveDirection;
                    best = v;
                }

                if (best+EPS > beta) {
                    break;
                }

                alpha = Math.Max(alpha,best);

            }
            Console.WriteLine("AlphaBetaSearch:");
            Console.WriteLine("  agent location:    {0}", agentLoc.ToString());
            Console.WriteLine("  opponent location: {0}", opponentLoc.ToString());
            Console.WriteLine("  SELECTED MOVE: {0}\n\n", bestMove);
            return bestMove;
        }
        
        private double maxValue(int[,] board,int depth,Vector2 agentLoc,Vector2 opponentLoc)
        {
            //if (isTerminal(board,agentLoc,opponentLoc))
            //{
            //    return utility(board,agentLoc,opponentLoc);
            //}
            // XXX memoization???

            double best = NEGATIVE_INFINITY;

            foreach (Vector2 possibleMoveDirection in Constants.PossibleMoveDirections)
            {
                Vector2 newLocation = new Vector2(opponentLoc.X + possibleMoveDirection.X, opponentLoc.Y + possibleMoveDirection.Y);


                if ( isValid(board,newLocation) )
                {
                    board[(int)newLocation.X, (int)newLocation.Y] = opponentIndex;
                    best = Math.Max(best, minValue(board, depth + 1, agentLoc, newLocation));
                    board[(int)newLocation.X, (int)newLocation.Y] = EMPTY_BLOCK;
                }
                else
                {
                    best = Math.Max(best, utility(board, agentLoc, newLocation));
                }
                if (best + EPS > beta)
                    return best;

                alpha = Math.Max(alpha, best);
            }

            return best;
        }

        private double minValue(int[,] board, int depth, Vector2 agentLoc, Vector2 opponentLoc)
        {
            //if (isTerminal(board, agentLoc, opponentLoc))
            //{
            //    return utility(board, agentLoc, opponentLoc);
            //}
            // XXX memoization???

            double best = POSITIVE_INFINITY;

            foreach (Vector2 possibleMoveDirection in Constants.PossibleMoveDirections)
            {
                Vector2 newLocation = new Vector2(agentLoc.X+possibleMoveDirection.X, agentLoc.Y+possibleMoveDirection.Y);

                if ( isValid(board,newLocation) )
                {
                    board[(int)newLocation.X, (int)newLocation.Y] = PlayerIndex;
                    best = Math.Min(best, maxValue(board, depth, newLocation, opponentLoc));
                    board[(int)newLocation.X, (int)newLocation.Y] = EMPTY_BLOCK;
                }
                else
                {
                    best = Math.Min(best, utility(board, newLocation, opponentLoc));
                }
                if (best + EPS < alpha)
                    return best;

                beta = Math.Min(beta, best);
            }
            return best;
        }

        private double utility(int[,] board, Vector2 agentLoc, Vector2 opponentLoc)
        {
            if (agentLoc.Equals(opponentLoc)) return 0;
            if (board[(int)agentLoc.X, (int)agentLoc.Y] != EMPTY_BLOCK)
                return -1;
            if (board[(int)opponentLoc.X, (int)opponentLoc.Y] != EMPTY_BLOCK)
                return 1;

            throw new ArgumentException("Cannot determine utility of a non-terminal state!");
        }

        private bool isTerminal(int[,] board, Vector2 agentLoc, Vector2 opponentLoc)
        {
            return board[(int)agentLoc.X, (int)agentLoc.Y] != EMPTY_BLOCK ||
                   board[(int)opponentLoc.X,(int) opponentLoc.Y] != EMPTY_BLOCK;
        }

        private bool isValid(int[,] board, Vector2 location)
        {
            return (board[(int)location.X, (int)location.Y] == EMPTY_BLOCK);
        }
    }
}
